Sau cách mạng Cuba ngày 01 tháng 01 năm 1959, Fidel Castro, một nhân vật bí ẩn đối với Liên Xô, trở thành Thủ tướng trong một nước Cuba mới. Từ sự lãnh đạo mới này, quan hệ giữa 02 quốc gia này đã chuyển thành đối tác chiến lược tin cậy trong khối cộng sản. Sau khi Liên Xô thiết lập lại mối quan hệ với Cuba sau giai đoạn gián đoạn, hàng loạt cuộc tiếp xúc ngoại giao giữa Cuba và các quốc gia Cộng sản trong năm 1960, mở ra nhiều mối quan hệ mới với Cuba. Việt Nam thiết lập với Cuba vào ngày 2 tháng 12 năm 1960, sau cuộc tiếp xúc giữa Thủ tướng Phạm Văn Đồng và bộ trưởng ngoại giao Cuba Raúl García.

Cuba ủng hộ Việt Nam trong cuộc chiến tranh chống đế quốc Mỹ. Trong cuộc chiến, Cuba đưa nhiều kỹ sư cầu đường xây dựng lại hệ thống đường sá bị tàn phá nặng nề, đưa các y bác sĩ cùng các loại thuốc men, dụng cụ y tế,... Cuộc chiến chống Mỹ của Việt Nam là nguồn cảm hứng cho nhiều lãnh đạo Cuba, một trong số đó là Che Guevara đã kêu gọi “phải tạo ra hai, ba, nhiều Việt Nam”. Năm 1973, sau khi Hiệp định Paris được kí kết, Fidel đã thăm vùng giải phóng của Việt Nam tại Quảng Trị và nhắc lại tuyên bố "Vì người Việt Nam, Cuba sẵn sàng hiến dâng cả máu của mình".

Chiến tranh biên giới 1979 nổ ra, Cuba tuyên bố ủng hộ Việt Nam chống Trung Quốc bành trướng đồng thời tuyên bố gửi quân sang Việt Nam. Từ giai đoạn 1980-1990, Việt Nam bị cấm vận, Cuba là một trong số ít quốc gia viện trợ thuốc men, vacxin, lương thực cho Việt Nam. Sau khi mở cửa nền kinh tế Việt Nam được phát triển, Việt Nam lại trở thành quốc gia viện trợ cho Cuba, và là quốc gia tích cực kêu gọi Mỹ chống bao vây cấm vận Cuba. Việt Nam tiếp tục viện trợ lương thực, thực phẩm, máy móc, và trang thiết bị. Từ giai đoạn 2010-2020, Cuba mở cửa và cập nhật theo mô hình kinh tế thị trường của Việt Nam.